package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/8 8:56
 */
public class C153 {

    // https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
    // 暴力解, 数组找最小值
    public static int findMin2(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }

    // 半个暴力法
    public static int findMin(int[] nums) {
        int k = 0;
        for (; k + 1 < nums.length && nums[k + 1] >= nums[k]; k++) {
        }
        k++;
        return k < nums.length ? nums[k] : nums[0];
    }

    // 二分法, 找到k节点
    public static int findMin3(int[] nums) {
        int l = 0, r = nums.length - 1, m;
        while (l < r) {
            m = l + ((r - l) >> 1);
            if(nums[m] < nums[r]) {
                r = m;
            }else {
                l = m+1;
            }
        }
        return nums[l];
    }


    // for test
    public static void main(String[] args) {
        int[] nums = {4,5,6,7,0,1,2};
        System.out.println(findMin(nums));
        System.out.println(findMin2(nums));
        System.out.println(findMin3(nums));
    }

}
